#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    int search(vector<int> &num, int target)
    {
        int length = num.size();
        int begin = 0;
        int end = length - 1;
        int middle = (begin + end) / 2;
        while (begin <= end)
        {
            if (num[middle] < target)
            {
                begin = middle + 1;
                middle = (begin + end) / 2;
            }
            else if (num[middle] > target)
            {
                end = middle - 1;
                middle = (begin + end) / 2;
            }
            else
            {
                return middle;
            }
        }
        return -1;
    }
};

int main()
{
    vector<int> num{-1, 0, 3, 5, 9, 12};
    int target = 9;
    Solution sol;
    cout << sol.search(num, target) << endl;
    return 0;
}